package model;

/**
 * This class has methods for solving the coin game using a very fast non-recursive algorithm that makes use of dynamic programming. The dynamic programming algorithm saves the solutions to a matrix which can be printed afterwards.
 * 
 * @author Karen Berntsen (s0815799)
 * @author Erik Stens (s0615374)
 */
public class CoinGameSolverDynamic implements CoinGameSolver {
	private int[]	coins;
	private int[][]	solutionMatrix;
	
	public CoinGameSolverDynamic(int[] coins) {
		this.coins = coins;
		solutionMatrix = new int[coins.length][coins.length];
	}
	
	/**
	 * Solving algorithm. Makes use of dynamic programming by iteratively filling a matrix of best solutions until the best solutions for each state of the game (each subset of consecutive coins) have been found.
	 * 
	 * @return the minimum value the first player should at least be able to get.
	 */
	@Override
	public int solve() {
		fillSolutionMatrixDiagonal();
		fillSolutionMatrixTotals();
		fillSolutionMatrixSolutions();
		
		int result = solutionMatrix[0][coins.length - 1];
		
		return result;
	}
	
	/**
	 * Puts the value of each coin into the diagonal of the solutionMatrix
	 */
	private void fillSolutionMatrixDiagonal() {
		for (int i = 0, size = coins.length; i < size; i++) {
			solutionMatrix[i][i] = coins[i];
		}
	}
	
	/**
	 * Calculates the sum of the coins in each subset of consecutive coins. Assumes that the solutionMatrix already contains the values of the coins.
	 */
	private void fillSolutionMatrixTotals() {
		for (int r = 0, size = coins.length; r < size - 1; r++) {
			for (int l = r + 1; l < size; l++) {
				solutionMatrix[l][r] = solutionMatrix[l - 1][r] + coins[l];
			}
		}
	}
	
	/**
	 * Calculates the best solution for each state of the game (each subset of consecutive coins). Assumes that the solutionMatrix already contains the values of the coins and the sum of the coins in each subset of consecutive coins.
	 */
	private void fillSolutionMatrixSolutions() {
		for (int i = 1, size = coins.length; i < size; i++) {
			for (int l = 0, r = i; r < size; l++, r++) {
				solutionMatrix[l][r] = solutionMatrix[r][l] - Math.min(solutionMatrix[l + 1][r], solutionMatrix[l][r - 1]);
			}
		}
	}
	
	/**
	 * Prints the solutionMatrix used in the second solving algorithm.
	 */
	public void printSolutionMatrix() {
		for (int[] i : solutionMatrix) {
			for (int j : i) {
				System.out.print(j + "\t");
			}
			System.out.print('\n');
		}
	}
	
	public void printBestStrategy() {
		printBestStrategy(0, coins.length - 1);
	}
	
	/**
	 * Prints the best strategy of taking coins, given a subset of the total line of coins. In a situation where a choice has no influence on the outcome, this strategy assumes the player takes the coin with the highest value.
	 * 
	 * @param lStart
	 * @param rStart
	 */
	public void printBestStrategy(int lStart, int rStart) {
		int l = lStart, r = rStart;
		while (l != r) {
			int diff = solutionMatrix[l + 1][r] - solutionMatrix[l][r - 1];
			if (diff == 0) {
				diff = solutionMatrix[r][r] - solutionMatrix[l][l];
			}
			
			if (diff <= 0) {
				System.out.println("Take left coin (index: " + l + ", value: " + coins[l] + ")");
				l++;
			} else if (diff > 0) {
				System.out.println("Take right coin (index: " + r + ", value: " + coins[r] + ")");
				r--;
			}
		}
		System.out.println("Take last coin (index: " + l + ", value: " + coins[l] + ")");
	}
}
